#include "dyArray.h"
#include<stdlib.h>
#include<time.h>
#include<iostream>
using namespace std;

void swap(int& a, int& b)
{
	int temp = b;
	b = a;
	a = temp;
}

int partition(int* array, int s, int t)
{
	int i = s, j = t;
	int temp = array[i];
	while (i<j)
	{
		while (i < j && array[j] >= temp)
		{
			j--;
		}
		swap(array[i], array[j]);
		while (i < j && array[i] <= temp)
		{
			i++;
		}
		swap(array[i], array[j]);
	}
	return i;
}

void DyArray::quickSort(int a, int b)
{
	int i;
	if (a<b)
	{
		i = partition(this->head, a, b);
		this->quickSort(i + 1, b);
		this->quickSort(a, i - 1);
	}
}

void DyArray::mergePass(int length)
{
	int i;
	for (i = 0; i+2*length-1 < this->length; i=i+2*length)
	{
		this->merge(i, i + length - 1, i + 2 * length - 1);
	}
	if (i+length-1<this->length)
	{
		this->merge(i, i + length - 1, this->length - 1);
	}
}

void DyArray::merge(int low, int mid, int high)
{
	int i = low, j = mid + 1, k = 0;
	int* array = new int[high - low + 1]();
	while (i<=mid && j<=high)
	{
		if (this->head[i] < this->head[j])
		{
			array[k] = this->head[i];
			k++; i++;
		}
		else
		{
			array[k] = this->head[j];
			k++; j++;
		}
	}
	while (i <= mid)
	{
		array[k] = this->head[i];
		k++; i++;
	}
	while (j <= high)
	{
		array[k] = this->head[j];
		k++; j++;
	}
	for (int h = 0; h < k; h++)
	{
		this->head[low] = array[h];
		low++;
	}
	delete[] array;
}

DyArray::DyArray()
{
	this->length = 0;
	this->head = new int[0];
}

DyArray::DyArray(int array[], int n)
{
	this->length = n;
	this->head = new int[n];
	for (int i = 0; i < n; i++)
	{
		head[i] = array[i];
	}
}

DyArray::DyArray(int n, initializationType type)
{
	int a;
	switch (type)
	{
	case Zero:
		this->length = n;
		this->head = new int[n]();
		break;
	case Random:
		this->length = n;
		this->head = new int[n];
		srand((int)time(0));
		for (int i = 0; i < n; i++)
		{
			a = rand() % 10000;
			this->head[i] = a;
		}
		break;
	case FixedRandom:
		this->length = n;
		this->head = new int[n];
		for (int i = 0; i < n; i++)
		{
			a = rand() % 10000000;
			this->head[i] = a;
		}
		break;
	default:
		this->length = n;
		this->head = new int[n]();
		break;
	}
}

DyArray::~DyArray()
{
	delete[] this->head;
}

bool DyArray::isEmpty()
{
	if (this->length==0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int DyArray::getLength()
{
	return this->length;
}

void DyArray::dispList(int n=20)
{
	int i = 0;
	for (int k=0 ; k<this->length ; k++)
	{
		cout << this->head[k] << " ";
		i++;
		i = i % n;
		if (i == 0)
		{
			cout << endl;
		}
	}
}

int DyArray::getElement(int i)
{
	return this->head[i];
}

void DyArray::insertElement(int e, int i)
{
	if (i<0 || i>this->length)
	{
		return;
	}
	int* n = new int[this->length + 1];
	for (int k = 0; k < i; k++)
	{
		n[k] = this->head[k];
	}
	n[i] = e;
	for (int k = i+1; k < this->length; k++)
	{
		n[k] = this->head[k-1];
	}
	this->length++;
	delete[] this->head;
	this->head = n;
}

void DyArray::insertSort()
{
	int temp, j;
	for (int i = 1; i < this->length; i++)
	{
		temp = this->head[i];
		j = i - 1;
		while (temp<this->head[j] && j>=0)
		{
			swap(this->head[j], this->head[j + 1]);
			j--;
		}
	}
}

void DyArray::binInsertSort()
{
	int temp, mid, high, low;
	for (int i = 1; i < this->length; i++)
	{
		high = i - 1;
		low = 0;
		temp = this->head[i];
		while (low<=high)
		{
			mid = (high + low) / 2;
			if (temp<this->head[mid])
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		for (int j = i - 1; j > high; j--)
		{
			swap(this->head[j], this->head[j + 1]);
		}
	}
}

void DyArray::shellSort()
{
	int d = this->length / 2;
	int temp, j;
	while (d>0)
	{
		for (int i = d; i < this->length; i++)
		{
			temp = this->head[i];
			j = i - d;
			while (j>=0 && temp<this->head[j])
			{
				swap(this->head[j], this->head[j + d]);
				j = j - d;
			}
		}
		d = d / 2;
	}
}

void DyArray::shellSort(int d, int n, shellReduceIncrementType type)
{
	switch (type)
	{
		int temp, j;
	case Subtraction:
		switch (d)
		{
		case 1:
			this->insertSort();
			break;
		default:
			if (d<=0)
			{
				break;
			}
			for (int i = d; i < this->length; i++)
			{
				temp = this->head[i];
				j = i - d;
				while (j >= 0 && temp < this->head[j])
				{
					swap(this->head[j], this->head[j + d]);
					j = j - d;
				}
			}
			d = d - n;
			if (d<0)
			{
				d = 1;
			}
		}
		break;
	case Division:
		while (d > 0)
		{
			for (int i = d; i < this->length; i++)
			{
				temp = this->head[i];
				j = i - d;
				while (j >= 0 && temp < this->head[j])
				{
					swap(this->head[j], this->head[j + d]);
					j = j - d;
				}
			}
			d = d / n;
		}
		break;
	default:
		this->insertSort();
		break;
	}
}

void DyArray::bubbleSort()
{
	for (int i = 0; i < this->length-1; i++)
	{
		for (int j = 0; j<this->length-1-i; j++)
		{
			if (this->head[j]>this->head[j+1])
			{
				swap(this->head[j], this->head[j + 1]);
			}
		}
	}
}

void DyArray::quickSort()
{
	int i, s = 0;
	int t = this->length - 1;
	if (s<t)
	{
		i = partition(this->head, s, t);
		this->quickSort(i + 1, t);
		this->quickSort(s, i - 1);
	}
}

void DyArray::mergeSort()
{
	int length = 1;
	while (length<this->length)
	{
		this->mergePass(length);
		length = length * 2;
	}
}


